package practice19;

import java.util.Stack;

public class Main {
    public static int solution(int n, int[] heights) {
        if (heights == null || heights.length == 0) {
            return 0;
        }

        int maxArea = 0;
        Stack<Integer> stack = new Stack<>();
        for (int i = 0; i <= n; i++) {
            // 当前高度小于栈顶元素的高度，或者已经遍历到最后一个元素
            while (!stack.isEmpty() && (i == n || heights[stack.peek()] >= heights[i])) {
                // 弹出栈顶元素
                int height = heights[stack.pop()];
                // 计算宽度
                int width = stack.isEmpty() ? i : i - stack.peek() - 1;
                // 计算面积
                maxArea = Math.max(maxArea, height * width);
            }
            // 将当前索引压入栈中
            stack.push(i);
        }

        return maxArea;
    }

    public static void main(String[] args) {
        // 测试样例
        System.out.println(solution(5, new int[]{1, 2, 3, 4, 5})); // 输出 9
        System.out.println(solution(6, new int[]{5, 4, 3, 2, 1, 6})); // 输出 9
        System.out.println(solution(4, new int[]{4, 4, 4, 4})); // 输出 16
    }
}